{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest String Starting From Leaf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #string #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #字符串 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestFromLeaf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从叶结点开始的最小字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一颗根结点为&nbsp;<code>root</code>&nbsp;的二叉树，树中的每一个结点都有一个&nbsp;<code>[0, 25]</code>&nbsp;范围内的值，分别代表字母&nbsp;<code>'a'</code> 到&nbsp;<code>'z'</code>。</p>\n",
    "\n",
    "<p>返回 <em><strong>按字典序最小</strong> 的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束</em>。</p>\n",
    "\n",
    "<blockquote>\n",
    "<p>注<strong>：</strong>字符串中任何较短的前缀在 <strong>字典序上</strong> 都是 <strong>较小</strong> 的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，在字典序上&nbsp;<code>\"ab\"</code> 比&nbsp;<code>\"aba\"</code>&nbsp;要小。叶结点是指没有子结点的结点。&nbsp;</li>\n",
    "</ul>\n",
    "</blockquote>\n",
    "\n",
    "<p>节点的叶节点是没有子节点的节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/02/tree1.png\" style=\"height: 358px; width: 534px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0,1,2,3,4,3,4]\n",
    "<strong>输出：</strong>\"dba\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2019/01/30/tree2.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [25,1,3,1,3,0,2]\n",
    "<strong>输出：</strong>\"adz\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2019/02/01/tree3.png\" style=\"height: 513px; width: 490px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,2,1,null,1,0,null,0]\n",
    "<strong>输出：</strong>\"abc\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>给定树的结点数在&nbsp;<code>[1, 8500]</code> 范围内</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 25</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-string-starting-from-leaf](https://leetcode.cn/problems/smallest-string-starting-from-leaf/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-string-starting-from-leaf](https://leetcode.cn/problems/smallest-string-starting-from-leaf/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,2,3,4,3,4]', '[25,1,3,1,3,0,2]', '[2,2,1,null,1,0,null,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        toStr = lambda a: chr(a + ord('a'))\n",
    "        def dfs(root: Optional[TreeNode], suffix: str, ans: List[str]):\n",
    "            suffix = toStr(root.val) + suffix\n",
    "            if not root.left and not root.right:\n",
    "                if not ans:\n",
    "                    ans.append(suffix)\n",
    "                else:\n",
    "                    ans[0] = min(ans[0], suffix)\n",
    "                return\n",
    "            if root.left:\n",
    "                dfs(root.left, suffix, ans)\n",
    "            if root.right:\n",
    "                dfs(root.right, suffix, ans)\n",
    "\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        ans = []\n",
    "        dfs(root, \"\", ans)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        d = {}\n",
    "        queue = deque([])\n",
    "        def dfs(root):\n",
    "            if root.left:\n",
    "                d[root.left] = root\n",
    "                dfs(root.left)\n",
    "            if root.right:\n",
    "                d[root.right] = root\n",
    "                dfs(root.right)\n",
    "            if not root.left and not root.right:\n",
    "                queue.append([chr(root.val+ord('a')), root])\n",
    "        dfs(root)\n",
    "        ans = ''\n",
    "        while queue:\n",
    "            tmp = min(x[0] for x in queue)\n",
    "            for _ in range(len(queue)):\n",
    "                val, node = queue.popleft()\n",
    "                if val == tmp and (ans == '' or val < ans):\n",
    "                    if node in d:\n",
    "                        queue.append([val+chr(d[node].val+ord('a')), d[node]])\n",
    "                    else:\n",
    "                        if ans == '' or val < ans:\n",
    "                            ans = val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        path = list()\n",
    "        ret = list()\n",
    "        word = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        result = \"\"\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            path.append(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                ret.append(path[:])\n",
    "\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            path.pop()\n",
    "\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        dfs(root)\n",
    "        begin = ret[0][:]\n",
    "        begin.reverse()\n",
    "        for i in begin:\n",
    "            result += word[i]\n",
    "        for each in ret:\n",
    "            each.reverse()\n",
    "            node_str = \"\"\n",
    "            for i in each:\n",
    "                node_str += word[i]\n",
    "            if node_str < result:\n",
    "                result = node_str\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \n",
    "            if not node.left and not node.right:\n",
    "                ret.append([chr(node.val + ord('a'))] + tmp[::-1])\n",
    "            tmp.append(chr(node.val + ord('a')))\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            tmp.pop()\n",
    "        \n",
    "        ret, tmp = [], []\n",
    "        dfs(root)\n",
    "        return \"\".join(min(ret))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = '~'\n",
    "        def dfs(root, s):\n",
    "            if not root:\n",
    "                return\n",
    "            ch = chr(ord('a') + root.val)\n",
    "            if not root.left and not root.right:\n",
    "                nonlocal ans\n",
    "                ans = min(ans, ch + s)\n",
    "            dfs(root.left, ch + s)\n",
    "            dfs(root.right, ch + s)\n",
    "        dfs(root, '')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = 'z' * 8500\n",
    "        def dfs(root, s):\n",
    "            if not root:\n",
    "                return\n",
    "            ch = chr(ord('a') + root.val)\n",
    "            if not root.left and not root.right:\n",
    "                nonlocal ans\n",
    "                ans = min(ans, ch + s)\n",
    "                return\n",
    "            dfs(root.left, ch + s)\n",
    "            dfs(root.right, ch + s)\n",
    "        dfs(root, '')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.res = '~'\n",
    "        self.path = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return ''\n",
    "            self.path.append(chr(node.val+ord('a')))\n",
    "            if not node.left and not node.right:\n",
    "                self.res = min(self.res,''.join(reversed(self.path)))\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            self.path.pop()\n",
    "        dfs(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = \"~\"\n",
    "        def dfs(node, s: list):\n",
    "            s.append(string.ascii_lowercase[node.val])\n",
    "            if not node.left and not node.right:\n",
    "                nonlocal ans\n",
    "                ans = min(ans, \"\".join(reversed(s)))\n",
    "            if node.left:\n",
    "                dfs(node.left, s)\n",
    "            if node.right:\n",
    "                dfs(node.right, s)\n",
    "            s.pop()\n",
    "        dfs(root, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: TreeNode) -> str:\n",
    "        self.ans = '~'\n",
    "        def helper(root,curr):\n",
    "            if root:\n",
    "                curr += chr(root.val+ord('a'))\n",
    "                if not root.left and not root.right:\n",
    "                    self.ans = min(self.ans,curr[::-1])\n",
    "                helper(root.left,curr)\n",
    "                helper(root.right,curr)\n",
    "        helper(root,'')\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        #一定是叶节点到根节点\n",
    "        tail = 26\n",
    "        res = []\n",
    "        def dfs(node,path):\n",
    "            nonlocal tail,res\n",
    "            if not node:\n",
    "                return \n",
    "            if not node.left and not node.right: #yezi\n",
    "                if node.val<tail:\n",
    "                    tail = node.val\n",
    "                    res = []\n",
    "                if node.val == tail:\n",
    "                    path.append(node.val)\n",
    "                    res.append(path[:])\n",
    "                    path.pop()\n",
    "                return\n",
    "            path.append(node.val)\n",
    "            dfs(node.left,path)\n",
    "            dfs(node.right,path)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(root,[])\n",
    "        # print(res)\n",
    "        final = set()\n",
    "        for p in res:\n",
    "            temp = ''\n",
    "            for i in range(len(p)-1,-1,-1):\n",
    "                temp += chr(ord('a')+p[i])\n",
    "            final.add(temp)\n",
    "\n",
    "        # print(final)\n",
    "        r = sorted(list(final))\n",
    "        return r[0] if r else []\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        self.ans = \"~\"\n",
    "\n",
    "        def dfs(node:TreeNode,res:list):\n",
    "            if node:\n",
    "                res.append(chr(node.val+ord('a')))\n",
    "                if not node.left and not node.right:\n",
    "                    self.ans=min(self.ans,\"\".join(reversed(res)))\n",
    "\n",
    "                dfs(node.left,res)\n",
    "                dfs(node.right,res)\n",
    "                res.pop()\n",
    "\n",
    "        \n",
    "        dfs(root,[])\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.ans= '~'\n",
    "        self.dfs(root,[])\n",
    "        return self.ans\n",
    "    def dfs(self,root,s):\n",
    "        if not root:\n",
    "            return \n",
    "        s.append(chr(ord('a') + root.val))\n",
    "        #叶子节点\n",
    "        if not root.left and not root.right:\n",
    "            self.ans = min(self.ans,\"\".join(reversed(s)))\n",
    "            # return\n",
    "        self.dfs(root.left,s)\n",
    "        self.dfs(root.right,s)\n",
    "        s.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        self.ans = \"~\"\n",
    "\n",
    "        def dfs(node:TreeNode,res:list):\n",
    "            if node:\n",
    "                res.append(chr(node.val+ord('a')))\n",
    "                if not node.left and not node.right:\n",
    "                    self.ans=min(self.ans,\"\".join(reversed(res)))\n",
    "\n",
    "                dfs(node.left,res)\n",
    "                dfs(node.right,res)\n",
    "                res.pop()\n",
    "\n",
    "        dfs(root,[])\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        res = 'zzzzzzzzzzzzzzzzzz'\n",
    "        def dfs(node,path):\n",
    "            nonlocal res\n",
    "            if not node.left and not node.right:\n",
    "                path += chr(node.val + ord('a'))\n",
    "                res = min(res,path[::-1])\n",
    "                return \n",
    "            else:\n",
    "                path += chr(node.val + ord('a'))\n",
    "                if node.left:\n",
    "                    dfs(node.left,path)\n",
    "                if node.right:\n",
    "                    dfs(node.right,path)\n",
    "                path = path[:-1]\n",
    "        dfs(root,'')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.ans = \"~\"\n",
    "\n",
    "        def dfs(node, A):\n",
    "            if node:\n",
    "                A.append(chr(node.val + 97))\n",
    "                if not (node.left or node.right):\n",
    "                    self.ans = min(self.ans, \"\".join(A)[::-1])\n",
    "\n",
    "                dfs(node.left, A)\n",
    "                dfs(node.right, A)\n",
    "                A.pop()\n",
    "\n",
    "        dfs(root, [])\n",
    "        return self.ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.res = None\n",
    "\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "    \n",
    "    def traverse(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        if not root.left and not root.right:\n",
    "            self.path.append(chr(ord('a')+root.val))\n",
    "            s= \"\".join(self.path[::-1])\n",
    "            if not self.res or self.res>s:\n",
    "                self.res = s\n",
    "            self.path.pop()\n",
    "            return\n",
    "        self.path.append(chr(ord('a')+root.val))\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "        self.path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: TreeNode) -> str:\n",
    "        self.path = []\n",
    "        self.res = None\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, root: TreeNode):\n",
    "        if not root:\n",
    "            return\n",
    "        if not root.left and not root.right:\n",
    "            # 找到叶子结点，比较字典序最小的路径\n",
    "            # 结果字符串是从叶子向根，所以需要反转\n",
    "            self.path.append(chr(ord('a') + root.val))\n",
    "            s = \"\".join(self.path[::-1])\n",
    "            if not self.res or self.res > s:\n",
    "                # 如果字典序更小，则更新 res\n",
    "                self.res = s\n",
    "            # 恢复，正确维护 path 中的元素\n",
    "            self.path.pop()\n",
    "            return\n",
    "        # 前序位置\n",
    "        self.path.append(chr(ord('a') + root.val))\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "        # 后序位置\n",
    "        self.path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        def compare(lp, rp):\n",
    "            if rp == \"\":\n",
    "                return True\n",
    "\n",
    "            ll = min(len(lp), len(rp))\n",
    "            for i in range(ll):\n",
    "                if lp[i] < rp[i]:\n",
    "                    return True\n",
    "                elif lp[i] > rp[i]:\n",
    "                    return False\n",
    "                else:\n",
    "                    pass\n",
    "            return len(lp) < len(rp)\n",
    "        \n",
    "        self.res = \"\"\n",
    "\n",
    "        def dfs(root, path):\n",
    "            if not root.left and not root.right:\n",
    "                path.append(chr(97 + root.val))\n",
    "                path_str = \"\".join(path[::-1])\n",
    "                \n",
    "                if compare(path_str, self.res):\n",
    "                    self.res = path_str\n",
    "                # print(path_str, res)\n",
    "                return \n",
    "\n",
    "     \n",
    "            if root.left:\n",
    "                dfs(root.left, path + [chr(97 + root.val)] )\n",
    "            \n",
    "            if root.right:\n",
    "                dfs(root.right, path + [chr(97 + root.val)])\n",
    "            return \n",
    "\n",
    "   \n",
    "        dfs(root, [])\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.ans = \"~\"\n",
    "        def dfs(root, path):\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.left and not root.right:\n",
    "                path = path + chr(root.val + ord(\"a\"))\n",
    "                self.ans = min(self.ans, path[::-1])\n",
    "            dfs(root.left, path + chr(root.val + ord(\"a\")))\n",
    "            dfs(root.right, path + chr(root.val + ord(\"a\")))\n",
    "        dfs(root, \"\")\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for a binary tree node.\n",
    "# # class TreeNode:\n",
    "# #     def __init__(self, val=0, left=None, right=None):\n",
    "# #         self.val = val\n",
    "# #         self.left = left\n",
    "# #         self.right = right\n",
    "# class Solution:\n",
    "#     def __init__(self):\n",
    "#         self._min_val = None\n",
    "    \n",
    "#     def find_min_char(self, root, cur_path):\n",
    "#         if root is not None:\n",
    "#             cur_path.append(chr(root.val + ord('a')))\n",
    "#             print(cur_path)\n",
    "#             cur_str = ''.join(cur_path[::-1])\n",
    "#             if root.left is None and root.right is None:\n",
    "#                 self._min_val = cur_str if self._min_val is None else min(cur_str, self._min_val)\n",
    "#             ori_len = len(cur_str)\n",
    "#             self.find_min_char(root.left, cur_path[:ori_len])           \n",
    "#             self.find_min_char(root.right, cur_path[:ori_len])\n",
    "\n",
    "#     def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "#         self.find_min_char(root, [])\n",
    "#         return self._min_val\n",
    "\n",
    "class Solution(object):\n",
    "    def smallestFromLeaf(self, root):\n",
    "        self.ans = \"~\"\n",
    "\n",
    "        def dfs(node, A):\n",
    "            if node:\n",
    "                A.append(chr(node.val + ord('a')))\n",
    "                if not node.left and not node.right:\n",
    "                    self.ans = min(self.ans, \"\".join(reversed(A)))\n",
    "\n",
    "                dfs(node.left, A)\n",
    "                dfs(node.right, A)\n",
    "                A.pop()\n",
    "\n",
    "        dfs(root, [])\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        def dfs(node):\n",
    "            # 后序遍历解决不了字典序问题, 用前序遍历要借助额外空间进行辅助, 这里用回溯算法\n",
    "            nonlocal ans\n",
    "            if not node: return\n",
    "            pre.append(node.val)\n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                if not ans or pre[::-1] < ans:\n",
    "                    ans = pre[::-1]\n",
    "\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            pre.pop()\n",
    "            return\n",
    "        \n",
    "        ans = []\n",
    "        pre = [] \n",
    "        dfs(root)\n",
    "        return \"\".join(chr(i + ord(\"a\")) for i in ans)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "    \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        q = []\n",
    "        b = ord('a')\n",
    "        def dfs(aRt, aDat):\n",
    "            nd = aDat + [chr(aRt.val + b)]\n",
    "            \n",
    "            if None == aRt.left and None == aRt.right:\n",
    "                heapq.heappush(q, \"\".join(nd[::-1]))\n",
    "            else:\n",
    "                if aRt.left != None:\n",
    "                    dfs(aRt.left, nd)\n",
    "                if aRt.right != None:\n",
    "                    dfs(aRt.right, nd)\n",
    "        dfs(root, [])\n",
    "        return q[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        res = None\n",
    "\n",
    "        def dfs(node, path):\n",
    "            c = chr(node.val+ord('a'))\n",
    "            path.append(c)\n",
    "            if not node.left and not node.right:\n",
    "                cur = ''.join(path[::-1])\n",
    "                nonlocal res\n",
    "                if not res:\n",
    "                    res = cur\n",
    "                else:\n",
    "                    res = min(res, cur)\n",
    "                path.pop()\n",
    "                return\n",
    "            \n",
    "            if node.left:\n",
    "                dfs(node.left, path)\n",
    "            if node.right:\n",
    "                dfs(node.right, path)\n",
    "            path.pop()\n",
    "        \n",
    "        dfs(root, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        def dfs(node):\n",
    "            # 后序遍历解决不了字典序问题, 用前序遍历要借助额外空间进行辅助, 这里用回溯算法\n",
    "            nonlocal ans\n",
    "            if not node: return\n",
    "            pre.append(node.val)\n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                if not ans or pre[::-1] < ans:\n",
    "                    ans = pre[::-1]\n",
    "\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            pre.pop()\n",
    "            return\n",
    "        \n",
    "        ans = []\n",
    "        pre = [] \n",
    "        dfs(root)\n",
    "        return \"\".join(chr(i + ord(\"a\")) for i in ans)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "    \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        def genStr(l):\n",
    "            return ''.join([chr(97+n) for n in l])\n",
    "\n",
    "        def dfs(path, node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            if not node.left and not node.right:\n",
    "                ans = min(ans, genStr([node.val]+path))\n",
    "                return\n",
    "            dfs([node.val]+path, node.left)\n",
    "            dfs([node.val]+path, node.right)\n",
    "        \n",
    "        ans = 'z'*8501\n",
    "        dfs([], root)\n",
    "        return ans\n",
    "\n",
    "        # def leafHeight(node):\n",
    "        #     if not node.left and not node.right:\n",
    "        #         node.val = [node.val, 1] # 最小叶高\n",
    "        #         return\n",
    "        #     min_leaf_height = 8501\n",
    "        #     if node.left:\n",
    "        #         leafHeight(node.left)\n",
    "        #         min_leaf_height = min(min_leaf_height, node.left.val[1]+1)\n",
    "        #     if node.right:\n",
    "        #         leafHeight(node.right)\n",
    "        #         min_leaf_height = min(min_leaf_height, node.right.val[1]+1)\n",
    "        #     node.val = [node.val, min_leaf_height]\n",
    "        \n",
    "        # def genStr(l):\n",
    "        #     return ''.join([chr(97+n) for n in l])\n",
    "\n",
    "        # def findPath(path, node):\n",
    "        #     nonlocal ans\n",
    "        #     if not node.left and not node.right:\n",
    "        #         ans = min(ans, genStr([node.val[0]]+path))\n",
    "        #     elif not node.left or not node.right: # 独臂\n",
    "        #         findPath([node.val[0]]+path, node.left or node.right)\n",
    "        #     elif node.left.val[1] < node.right.val[1]:\n",
    "        #         findPath([node.val[0]]+path, node.left)\n",
    "        #     elif node.left.val[1] > node.right.val[1]:\n",
    "        #         findPath([node.val[0]]+path, node.right)\n",
    "        #     # elif node.left.val[0] < node.right.val[0]:\n",
    "        #     #     findPath([node.val[0]]+path, node.left)\n",
    "        #     # elif node.left.val[0] > node.right.val[0]:\n",
    "        #     #     findPath([node.val[0]]+path, node.right)\n",
    "        #     else: # 两边叶小高度相同, char相同\n",
    "        #         findPath([node.val[0]]+path, node.left)\n",
    "        #         findPath([node.val[0]]+path, node.right)\n",
    "\n",
    "        # leafHeight(root)\n",
    "        # ans = 'z'*8501\n",
    "        # findPath([], root)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = 'z' * 8500\n",
    "        def dfs(root, s):\n",
    "            if not root:\n",
    "                return\n",
    "            ch = chr(ord('a') + root.val)\n",
    "            if not root.left and not root.right:\n",
    "                nonlocal ans\n",
    "                ans = min(ans, ch + s)\n",
    "                return\n",
    "            dfs(root.left, ch + s)\n",
    "            dfs(root.right, ch + s)\n",
    "        dfs(root, '')\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.res = chr(ord('a') + 26)\n",
    "\n",
    "        self.traverse(root, [])\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, path):\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        path.insert(0, chr(root.val + ord('a')))\n",
    "        if root.left is None and root.right is None:\n",
    "            s = \"\".join(path)\n",
    "            self.res = min(self.res, s)\n",
    "\n",
    "        self.traverse(root.left, path)\n",
    "        self.traverse(root.right, path)\n",
    "\n",
    "        path.pop(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: TreeNode) -> str:\n",
    "        self.path = []\n",
    "        self.res = None\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, root: TreeNode):\n",
    "        if not root:\n",
    "            return\n",
    "        self.path.append(chr(ord('a') + root.val))\n",
    "        if not root.left and not root.right:\n",
    "            s = \"\".join(self.path[::-1])\n",
    "            if not self.res or self.res > s:\n",
    "                # 如果字典序更小，则更新 res\n",
    "                self.res = s\n",
    "            # 恢复，正确维护 path 中的元\n",
    "        # 前序位置\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "        # 后序位置\n",
    "        self.path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.ans = \"~\"\n",
    "\n",
    "        def dfs(node, A):\n",
    "            if node:\n",
    "                A.append(chr(node.val + ord('a')))\n",
    "                if not node.left and not node.right:\n",
    "                    self.ans = min(self.ans, \"\".join(reversed(A)))\n",
    "\n",
    "                dfs(node.left, A)\n",
    "                dfs(node.right, A)\n",
    "                A.pop()\n",
    "\n",
    "        dfs(root, [])\n",
    "        return self.ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        res = chr(ord('z') + 1)\n",
    "        path = []\n",
    "\n",
    "        def backtrace(rt: TreeNode) -> None:\n",
    "            nonlocal res\n",
    "            nonlocal path\n",
    "            if not rt: return\n",
    "            \n",
    "            path.append(chr(ord('a') + rt.val))\n",
    "            if rt.left == None and rt.right == None:\n",
    "                res = min(res, ''.join(path[::-1]))\n",
    "            \n",
    "            backtrace(rt.left)\n",
    "            backtrace(rt.right)\n",
    "            \n",
    "            path.pop()        \n",
    "\n",
    "        backtrace(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: TreeNode) -> str:\n",
    "        res = chr(ord('z') + 1)\n",
    "        path = []\n",
    "\n",
    "        def backtrace(rt: TreeNode) -> None:\n",
    "            nonlocal res\n",
    "            nonlocal path\n",
    "\n",
    "            if rt:\n",
    "                path.append(chr(ord('a') + rt.val))\n",
    "                if rt.left == None and rt.right == None:\n",
    "                    res = min(res, ''.join(path[::-1]) )\n",
    "                \n",
    "                backtrace(rt.left)\n",
    "                backtrace(rt.right)\n",
    "                \n",
    "                path.pop()        \n",
    "\n",
    "        backtrace(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.ans = \"~\"\n",
    "\n",
    "        def dfs(node, A):\n",
    "            if node:\n",
    "                A.append(chr(node.val + ord('a')))\n",
    "                if not node.left and not node.right:\n",
    "                    self.ans = min(self.ans, \"\".join(reversed(A)))\n",
    "\n",
    "                dfs(node.left, A)\n",
    "                dfs(node.right, A)\n",
    "                A.pop()\n",
    "\n",
    "        dfs(root, [])\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = \"\"\n",
    "        self.path = \"\"\n",
    "        # self\n",
    "        self.depth = 0\n",
    "        self.max_depth = 0\n",
    "\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "    \n",
    "    def traverse(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.depth += 1\n",
    "        char = chr(ord('a') + root.val)\n",
    "        self.path = char + self.path\n",
    "        if not root.left and not root.right and self.max_depth==0:\n",
    "            self.max_depth = max(self.depth,self.max_depth)\n",
    "            self.res = self.path\n",
    "        elif not root.left and not root.right and self.max_depth>0:\n",
    "            if self.path < self.res:\n",
    "                self.res = self.path\n",
    "        \n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "        self.depth -= 1\n",
    "        self.path = self.path[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        res = []\n",
    "        res_all = []\n",
    "\n",
    "        def backtrace(root):\n",
    "            if not root : return \n",
    "            res.append(chr(ord('a')+root.val))\n",
    "            if not root.left and not root.right:\n",
    "                res_all.append(''.join(res[::-1]))\n",
    "            backtrace(root.left)\n",
    "            backtrace(root.right)\n",
    "            res.pop()\n",
    "\n",
    "        backtrace(root)\n",
    "        return min(res_all)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "      ret=\"\"\n",
    "      def dfs(root:Optional[TreeNode],cur_path:str):\n",
    "        if not root: return\n",
    "        nonlocal ret\n",
    "        cur_path+=chr(root.val+97)\n",
    "        if not root.left and not root.right:\n",
    "          rvsd_path=cur_path[::-1]\n",
    "          if len(ret)==0:\n",
    "            ret=rvsd_path\n",
    "          ret=min(ret,rvsd_path)\n",
    "        dfs(root.left,cur_path)\n",
    "        dfs(root.right,cur_path)\n",
    "      dfs(root,\"\")\n",
    "      return ret\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = \"~\"\n",
    "        def dfs(node, res):\n",
    "            nonlocal ans\n",
    "            if node:\n",
    "                res.append(chr(node.val + ord('a')))\n",
    "                if not node.left and not node.right:\n",
    "                    ans = min(ans, \"\".join(reversed(res)))\n",
    "                dfs(node.left, res)\n",
    "                dfs(node.right, res)\n",
    "                res.pop()\n",
    "        dfs(root, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.ret = \"{\"\n",
    "        def parse(root, p=\"\"):\n",
    "            now = chr(root.val + 97) + p\n",
    "            if root.left is None and root.right is None:\n",
    "                self.ret = min(self.ret, now)\n",
    "                return\n",
    "            if root.left: parse(root.left, now)\n",
    "            if root.right: parse(root.right, now)\n",
    "\n",
    "        parse(root)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        def dfs(root, path):\n",
    "            if not root:\n",
    "                return\n",
    "            path += chr(ord('a') + root.val)\n",
    "            if not root.left and not root.right:\n",
    "                res.append(path[::-1])\n",
    "            dfs(root.left, path)\n",
    "            dfs(root.right, path)\n",
    "        res = []\n",
    "        dfs(root, '')\n",
    "        res.sort()\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        # print(myhash)\n",
    "        def find_path(node,path):\n",
    "            if node:\n",
    "                path+=str(myhash[node.val])\n",
    "                # print(node.val,path)\n",
    "                if not node.left and not node.right:\n",
    "                    minleaf[0] = min(minleaf[0],path[::-1])\n",
    "                else:\n",
    "                    find_path(node.left,path)\n",
    "                    find_path(node.right,path)\n",
    "        myhash = {i: chr(ord('a') + i) for i in range(26)}\n",
    "        minleaf = [\"z\"*8500]\n",
    "        find_path(root,\"\")\n",
    "        return minleaf[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 记录所有从【叶子结点】到【根节点】的路径\n",
    "        self.res=[]\n",
    "        # 记录当前路径\n",
    "        self.path=[]\n",
    "\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        self.traverse(root)\n",
    "        self.res.sort()\n",
    "        print(self.res)\n",
    "        return self.res[0]\n",
    "    \n",
    "    def traverse(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        # 选择\n",
    "        self.path.append(self.convertToStr(root.val))\n",
    "        # 如果是叶子结点，则记录路径\n",
    "        if not root.left and not root.right:\n",
    "            self.res.append(\"\".join(self.path)[::-1])\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "        # 撤销选择\n",
    "        self.path.pop()\n",
    "        \n",
    "    \n",
    "    def convertToStr(self,num):\n",
    "        return chr(num+97)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        path = []\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            nonlocal res, path\n",
    "            if not root.left and not root.right:\n",
    "                path.append((chr(root.val + ord('a'))))\n",
    "                res.append(\"\".join(reversed(path.copy())))\n",
    "                path.pop()\n",
    "            path.append((chr(root.val + ord('a'))))\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            path.pop()\n",
    "        dfs(root)\n",
    "        return sorted(res)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\r\n",
    "        self.res = \"\"\r\n",
    "        self.tmp = []\r\n",
    "        self.traverse(root)\r\n",
    "        return self.res\r\n",
    "\r\n",
    "    def traverse(self, root):\r\n",
    "        if not root:\r\n",
    "            return\r\n",
    "\r\n",
    "        self.tmp.append(chr(ord(\"a\") + int(root.val)))\r\n",
    "\r\n",
    "        if not root.left and not root.right:\r\n",
    "            if \"\" == self.res:\r\n",
    "                self.res = \"\".join(self.tmp[::-1])\r\n",
    "            else:\r\n",
    "                tmp_str = \"\".join(self.tmp[::-1])\r\n",
    "                if self.res > tmp_str:\r\n",
    "                    self.res = tmp_str\r\n",
    "        self.traverse(root.left)\r\n",
    "        self.traverse(root.right)\r\n",
    "        self.tmp = self.tmp[:-1]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.path = []\n",
    "        self.res = None\n",
    "        self.trav(root)\n",
    "        return self.res\n",
    "\n",
    "    def trav(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        if root.left == root.right:\n",
    "            self.path.append(chr(ord('a') + root.val))\n",
    "            s = ''.join(self.path[::-1])\n",
    "            if not self.res or self.res > s:\n",
    "                self.res = s \n",
    "            self.path.pop() \n",
    "            return \n",
    "        self.path.append(chr(ord('a') + root.val))\n",
    "        self.trav(root.left)\n",
    "        self.trav(root.right)\n",
    "        self.path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        def dfs(node, path):\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            path = chr(node.val + 97) + path\n",
    "            \n",
    "            if not node.left and not node.right:\n",
    "                result.append(path)\n",
    "            \n",
    "            dfs(node.left, path)\n",
    "            dfs(node.right, path)\n",
    "        \n",
    "        result = []\n",
    "        dfs(root, \"\")\n",
    "        return min(result) if result else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.res = chr(26 + ord('a'))\n",
    "\n",
    "        self.traverse(root, [])\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, path):\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        path.insert(0, chr(root.val + ord('a')))\n",
    "\n",
    "        if root.left is None and root.right is None:\n",
    "            path_str = \"\".join(path)\n",
    "            self.res = min(path_str, self.res)\n",
    "\n",
    "        self.traverse(root.left, path)\n",
    "        self.traverse(root.right, path)\n",
    "\n",
    "        path.pop(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        result = []\n",
    "        temp = []\n",
    "        def dfs(root):\n",
    "            if not root.left and not root.right:\n",
    "                temp.append(chr(root.val + 97))\n",
    "                result.append(''.join(temp))\n",
    "                temp.pop()\n",
    "                return\n",
    "            if root.left:\n",
    "                temp.append(chr(root.val + 97))\n",
    "                dfs(root.left)\n",
    "                temp.pop()\n",
    "            if root.right:\n",
    "                temp.append(chr(root.val + 97))\n",
    "                dfs(root.right)\n",
    "                temp.pop()\n",
    "        dfs(root)\n",
    "        return min(map(lambda x: x[::-1], result))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.ans = \"~\"\n",
    "        def dfs(node, A):\n",
    "            if node:\n",
    "                A.append(chr(node.val + ord('a')))\n",
    "                if not node.left and not node.right:\n",
    "                    self.ans = min(self.ans, \"\".join(reversed(A)))\n",
    "\n",
    "                dfs(node.left, A)\n",
    "                dfs(node.right, A)\n",
    "                A.pop()\n",
    "\n",
    "        dfs(root, [])\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        ans=[]\n",
    "        def check(root,f):\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.left and not root.right:\n",
    "                f+=chr(root.val+97)\n",
    "                ans.append(f)\n",
    "                return\n",
    "            else:\n",
    "                check(root.left,f+chr(root.val+97))\n",
    "                check(root.right,f+chr(root.val+97))\n",
    "        check(root,'')\n",
    "        f=[]\n",
    "        for i in ans:\n",
    "            f.append(i[::-1])\n",
    "        return min(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        path = []\n",
    "        res = []\n",
    "    \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            if not root.left and not root.right:\n",
    "                path.append(chr(97 + int(root.val)))\n",
    "                # temp = []\n",
    "                # temp += path\n",
    "                # temp.reverse()\n",
    "                res.append(''.join(path)[::-1])\n",
    "                path.pop()\n",
    "                return\n",
    "            path.append(chr(97 + int(root.val)))\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            path.pop()\n",
    "    \n",
    "        dfs(root)\n",
    "        print(res)\n",
    "        return sorted(res)[0]\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "LOWERCHAR = 'abcdefghijklmnopqrstuvwxyz'\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        def check(root, pre):\n",
    "            print(root.val, pre)\n",
    "            if (not root.left) and (not root.right):\n",
    "                return LOWERCHAR[root.val]\n",
    "            if root.left and root.right:\n",
    "                l = check(root.left, LOWERCHAR[root.val]) + LOWERCHAR[root.val]\n",
    "                r = check(root.right, LOWERCHAR[root.val]) + LOWERCHAR[root.val]\n",
    "                if l + pre > r + pre:\n",
    "                    return r\n",
    "                else:\n",
    "                    return l\n",
    "            if root.left:\n",
    "                return check(root.left, LOWERCHAR[root.val]) + LOWERCHAR[root.val]\n",
    "            if root.right:\n",
    "                return check(root.right, LOWERCHAR[root.val]) + LOWERCHAR[root.val]\n",
    "        \n",
    "        return check(root, \"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.ans = \"~\"\n",
    "\n",
    "        def dfs(node, A):\n",
    "            if node:\n",
    "                A.append(chr(node.val + ord('a')))\n",
    "                if not node.left and not node.right:\n",
    "                    self.ans = min(self.ans, \"\".join(reversed(A)))\n",
    "\n",
    "                dfs(node.left, A)\n",
    "                dfs(node.right, A)\n",
    "                A.pop()\n",
    "\n",
    "        dfs(root, [])\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: TreeNode) -> str:\n",
    "        res = []\n",
    "        def dfs(root, path):\n",
    "            if not root:\n",
    "                return \n",
    "            letter = chr(root.val + 97)\n",
    "            path = letter + path\n",
    "            if not root.right and not root.left:\n",
    "                res.append(path)\n",
    "            dfs(root.left, path)\n",
    "            dfs(root.right, path)\n",
    "        dfs(root, '')\n",
    "        return min(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        \n",
    "        res = []\n",
    "        def dfs(root, path):\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.left and not root.right:\n",
    "                path.append(chr(root.val + 97))\n",
    "                res.append(''.join(path[::-1]))\n",
    "                path.pop()\n",
    "                return\n",
    "\n",
    "            path.append(chr(root.val + 97))\n",
    "            dfs(root.left, path)\n",
    "            dfs(root.right, path)\n",
    "            path.pop()\n",
    "        \n",
    "\n",
    "        dfs(root, [])\n",
    "        res.sort()\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.cur_path = []\n",
    "        self.answer = []\n",
    "\n",
    "        def compaer(old, new):\n",
    "            print(old, new)\n",
    "            for i in range(-1, -min(len(old), len(new))-1, -1):\n",
    "                print(i, new[i], old[i])\n",
    "                if new[i] < old[i]:\n",
    "                    return new\n",
    "                elif new[i] == old[i]:\n",
    "                    continue\n",
    "                else:\n",
    "                    return old\n",
    "            if len(new) < len(old):\n",
    "                return new\n",
    "            return old\n",
    "\n",
    "        def travel(root):\n",
    "            if not root:\n",
    "                return\n",
    "            self.cur_path.append(root.val)\n",
    "            travel(root.left)\n",
    "            travel(root.right)\n",
    "            if not root.left and not root.right:\n",
    "                if not len(self.answer):\n",
    "                    self.answer = self.cur_path\n",
    "                else:\n",
    "                    self.answer = compaer(self.answer, self.cur_path)\n",
    "            self.cur_path = self.cur_path[:-1]\n",
    "        travel(root)\n",
    "        return ''.join(list(map(chr, [i + 97 for i in reversed(self.answer)])))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def smallestFromLeaf(self, root):\n",
    "        res = []\n",
    "        def transform(a):\n",
    "            return chr(a + 97)\n",
    "\n",
    "        def dfs(root, s):\n",
    "            s.append(transform(root.val))\n",
    "            if not root.left and not root.right:\n",
    "                res.append(\"\".join(reversed(s)))\n",
    "                return\n",
    "            if root.left:\n",
    "                dfs(root.left, s)\n",
    "                s.pop()\n",
    "            if root.right:\n",
    "                dfs(root.right, s)\n",
    "                s.pop()\n",
    "        dfs(root, [])\n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        if not root:\n",
    "            return ''\n",
    "        \n",
    "        dic = {}\n",
    "        for i in range(26):\n",
    "            dic[i] = chr(ord('a') + i)\n",
    "\n",
    "        ans = []\n",
    "        path = []\n",
    "\n",
    "        def dfs(node):\n",
    "        \n",
    "            if node.left is None and node.right is None:\n",
    "                path.append(dic[node.val])\n",
    "                ans.append(''.join(path[::-1]))\n",
    "                return\n",
    "            \n",
    "            path.append(dic[node.val])\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "                path.pop()\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(root)\n",
    "        \n",
    "        a = ''\n",
    "        for i in range(len(ans)):\n",
    "            if i == 0:\n",
    "                a = ans[i]\n",
    "            else:\n",
    "                # if len(ans[i]) < len(a) or (len(ans[i]) == len(a) and ans[i] < a):\n",
    "                #     a = ans[i]\n",
    "                if ans[i] < a:\n",
    "                    a = ans[i]\n",
    "        return a\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        # res = []\n",
    "        # def dfs(root, path):\n",
    "        #     if not root:\n",
    "        #         return \n",
    "        #     letter = chr(root.val + 97)\n",
    "        #     path = letter + path\n",
    "        #     if root.right or root.left:\n",
    "        #         dfs(root.right, path)\n",
    "        #         dfs(root.left, path)\n",
    "        #     else:\n",
    "        #         res.append(path)\n",
    "        # dfs(root, '')\n",
    "        # return min(res)\n",
    "        res = []\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        queue = [(root, chr(root.val+97))]\n",
    "        while queue:\n",
    "            node, ans = queue.pop(0)\n",
    "            if not node.right and not node.left:\n",
    "                res.append(ans[::-1])\n",
    "            if node.left:\n",
    "                queue.append((node.left, ans+chr(node.left.val+97)))\n",
    "            if node.right:\n",
    "                queue.append((node.right, ans + chr(node.right.val + 97)))\n",
    "            \n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = []\n",
    "        def dfs(self, root, s):\n",
    "            if not root: return \n",
    "            if not root.left and not root.right:\n",
    "                s += chr(root.val + 97)\n",
    "                ans.append(s)\n",
    "            \n",
    "            dfs(self, root.left, s + chr(root.val + 97))\n",
    "            dfs(self, root.right, s + chr(root.val + 97))\n",
    "        \n",
    "        dfs(self, root, '')\n",
    "\n",
    "        return min([i[::-1] for i in ans])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        def g(r):\n",
    "          if r is None:\n",
    "              return []\n",
    "          if r.left is None and r.right is None:\n",
    "              return [chr(r.val+97)]\n",
    "          c=[]\n",
    "          x1,x2=g(r.left),g(r.right)\n",
    "          for x in x1:\n",
    "             if x1: \n",
    "              c.append(x+chr(r.val+97))\n",
    "          for x in x2:\n",
    "             if x2: \n",
    "              c.append(x+chr(r.val+97))\n",
    "          return c\n",
    "        rc=g(root) \n",
    "        for x in rc:\n",
    "            x=x[::-1]\n",
    "        rc.sort(key=lambda x:(x,len(x)))    \n",
    "        return rc[0]        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    \n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        stack = []\n",
    "        candidates = []\n",
    "        def find(root):\n",
    "            # base case\n",
    "            if not root:\n",
    "                return\n",
    "            stack.append(root.val)\n",
    "            if root and not root.left and not root.right:\n",
    "                candidates.append(stack[::-1])\n",
    "                stack.pop()\n",
    "                return\n",
    "            find(root.left)\n",
    "            find(root.right)\n",
    "            stack.pop()\n",
    "        find(root)\n",
    "        candidates = [[chr(ord('a') + val) for val in can] for can in candidates]\n",
    "        candidates = [''.join(can) for can in candidates]\n",
    "        return min(candidates, default = '')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def dfs(self, root, tmp):\n",
    "        if root.left==None and root.right==None:\n",
    "            self.res.append(tmp)\n",
    "            return\n",
    "        if root.left:\n",
    "            self.dfs(root.left, chr(97+root.left.val)+tmp)\n",
    "        if root.right:\n",
    "            self.dfs(root.right, chr(97+root.right.val)+tmp)\n",
    "        \n",
    "\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.dfs(root, chr(97+root.val))\n",
    "        self.res.sort()\n",
    "        return self.res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        parent = collections.defaultdict(TreeNode)\n",
    "        parent[root] = None\n",
    "        stack = [root]\n",
    "        leaf = []\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for cur in stack:\n",
    "                if not cur.left and not cur.right:\n",
    "                    while leaf and leaf[-1].val > cur.val:\n",
    "                        leaf.pop()\n",
    "                    if not leaf or cur.val == leaf[0].val:  leaf.append(cur)\n",
    "                    continue\n",
    "                if cur.left:    \n",
    "                    parent[cur.left] = cur\n",
    "                    temp.append(cur.left)\n",
    "                if cur.right:   \n",
    "                    parent[cur.right] = cur\n",
    "                    temp.append(cur.right)\n",
    "            stack = temp\n",
    "\n",
    "        pattern = []\n",
    "        while leaf:\n",
    "            temp = []\n",
    "            pattern.append(chr(leaf[0].val + ord(\"a\")))\n",
    "            for cur in leaf:\n",
    "                if not parent[cur]: return \"\".join(pattern)\n",
    "                while temp and temp[-1].val > parent[cur].val:\n",
    "                    temp.pop()\n",
    "                if not temp or temp[-1].val == parent[cur].val:  temp.append(parent[cur])\n",
    "            leaf = temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def to_chr(self, s):\n",
    "        return chr(ord('a') + s)\n",
    "\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        q = Queue()\n",
    "        q.put((root, self.to_chr(root.val)))\n",
    "        min_s = None\n",
    "        while not q.empty():\n",
    "            node, s = q.get()\n",
    "            if node.left is not None:\n",
    "                q.put((node.left, self.to_chr(node.left.val) + s))\n",
    "            if node.right is not None:\n",
    "                q.put((node.right, self.to_chr(node.right.val) + s))\n",
    "            if node.left is None and node.right is None:\n",
    "                if min_s is None:\n",
    "                    min_s = s\n",
    "                else:\n",
    "                    min_s = min(min_s, s)\n",
    "        return min_s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        parent = collections.defaultdict(TreeNode)\n",
    "        parent[root] = None\n",
    "        stack = [root]\n",
    "        leaf = []\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for cur in stack:\n",
    "                if not cur.left and not cur.right:\n",
    "                    while leaf and leaf[-1].val > cur.val:\n",
    "                        leaf.pop()\n",
    "                    if not leaf or cur.val == leaf[0].val:  leaf.append(cur)\n",
    "                    continue\n",
    "                if cur.left:    \n",
    "                    parent[cur.left] = cur\n",
    "                    temp.append(cur.left)\n",
    "                if cur.right:   \n",
    "                    parent[cur.right] = cur\n",
    "                    temp.append(cur.right)\n",
    "            stack = temp\n",
    "\n",
    "        pattern = []\n",
    "        while leaf:\n",
    "            temp = []\n",
    "            pattern.append(chr(leaf[0].val + ord(\"a\")))\n",
    "            for cur in leaf:\n",
    "                if not parent[cur]: return \"\".join(pattern)\n",
    "                while temp and temp[-1].val > parent[cur].val:\n",
    "                    temp.pop()\n",
    "                if not temp or temp[-1].val == parent[cur].val:  temp.append(parent[cur])\n",
    "            leaf = temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = []\n",
    "        def dfs(self, root, s):\n",
    "            if not root: return \n",
    "            if not root.left and not root.right:\n",
    "                s += chr(root.val + 97)\n",
    "                ans.append(s)\n",
    "            else:\n",
    "                dfs(self, root.left, s + chr(root.val + 97))\n",
    "                dfs(self, root.right, s + chr(root.val + 97))\n",
    "        \n",
    "        dfs(self, root, '')\n",
    "\n",
    "        return min([i[::-1] for i in ans])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.paths=[]\n",
    "\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        # * 反转字符串+排序+不回溯？\n",
    "        self.dfs(root,\"\")\n",
    "        self.paths.sort()\n",
    "        return self.paths[0]\n",
    "\n",
    "    #path:从根节点到当前节点的路径\n",
    "    def dfs(self,root: Optional[TreeNode],path:str):\n",
    "        if not  root:\n",
    "            return\n",
    "        #path+=str(ord('a')+root.val)\n",
    "        #**下面这行代码实际上创建了一个新的字符串，这个新字符串包含了 path 的内容和额外的内容。这个操作不会影响到原来的 path\n",
    "        #在Python中，字符串是不可变的，这意味着你不能修改一个字符串，只能创建一个新的字符串。\n",
    "        # 当你执行 s += chr(ord('a') + root.val) 这行代码时，你并没有改变原来的 s，而是创建了一个新的字符串，这个新字符串包含了 s 的内容和 'a' + root.val 这个字符。\n",
    "        path+=chr(ord('a')+root.val)\n",
    "        if root.left is None and root.right is None:\n",
    "            # 到达叶子结点，则要反转了\n",
    "            self.paths.append(path[::-1])\n",
    "        #**这两行代码中传递 s 时，你实际上是在传递 s 的一个副本。这个副本是在 s += chr(ord('a') + root.val) 这行代码中创建的。\n",
    "        # 这就是为什么你不需要进行回溯的原因，因为每次递归调用都有自己的 s，不会影响到其他的递归调用。\n",
    "        self.dfs(root.left,path)\n",
    "        self.dfs(root.right,path)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''chr(ord('a') + root.val) 和 str(ord('a') + root.val) 的主要区别在于它们的输出类型和内容。\n",
    "    1. chr(ord('a') + root.val)：这段代码首先获取字符 'a' 的ASCII值（97），然后加上 root.val（假设为2），得到99。然后，它使用 chr 函数将这个数值转换回字符，得到 'c'。所以，这段代码的输出是一个字符。\n",
    "\n",
    "    2. str(ord('a') + root.val)：这段代码首先获取字符 'a' 的ASCII值（97），然后加上 root.val（假设为2），得到99。然后，它使用 str 函数将这个数值转换为字符串，得到 '99'。所以，这段代码的输出是一个字符串，这个字符串表示一个整数。\n",
    "\n",
    "    所以，这两段代码的主要区别在于：chr(ord('a') + root.val) 输出的是一个字符，这个字符的ASCII值是 'a' 的ASCII值加上 root.val；而 str(ord('a') + root.val) 输出的是一个字符串，这个字符串表示一个整数，这个整数是 'a' 的ASCII值加上 root.val。\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        self.traverse(root, '')\n",
    "        return sorted(self.res, key=lambda x: x)[0]\n",
    "\n",
    "    def traverse(self, root, path):\n",
    "        if not root:\n",
    "            return\n",
    "        if root.left is None and root.right is None:\n",
    "            self.res.append(chr(root.val + ord('a')) + path)\n",
    "        self.traverse(root.left, chr(root.val + ord('a')) + path)\n",
    "        self.traverse(root.right, chr(root.val + ord('a')) + path)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        parent = collections.defaultdict(TreeNode)\n",
    "        parent[root] = None\n",
    "        stack = [root]\n",
    "        leaf = []\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for cur in stack:\n",
    "                if not cur.left and not cur.right:\n",
    "                    while leaf and leaf[-1].val > cur.val:\n",
    "                        leaf.pop()\n",
    "                    if not leaf or cur.val == leaf[0].val:  leaf.append(cur)\n",
    "                    continue\n",
    "                if cur.left:    \n",
    "                    parent[cur.left] = cur\n",
    "                    temp.append(cur.left)\n",
    "                if cur.right:   \n",
    "                    parent[cur.right] = cur\n",
    "                    temp.append(cur.right)\n",
    "            stack = temp\n",
    "\n",
    "        pattern = []\n",
    "        while leaf:\n",
    "            temp = []\n",
    "            pattern.append(chr(leaf[0].val + ord(\"a\")))\n",
    "            for cur in leaf:\n",
    "                if not parent[cur]: return \"\".join(pattern)\n",
    "                while temp and temp[-1].val > parent[cur].val:\n",
    "                    temp.pop()\n",
    "                if not temp or temp[-1].val == parent[cur].val:  temp.append(parent[cur])\n",
    "            leaf = temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    import copy\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        \n",
    "        def  check(root,ans):\n",
    "            if not root:\n",
    "                return \n",
    "            elif not root.left and not root.right:\n",
    "                ans.append(chr(root.val+97))\n",
    "                result.append(ans)\n",
    "                return \n",
    "            else:\n",
    "                check(root.left,ans+[chr(97+root.val)])\n",
    "                check(root.right,ans+[chr(97+root.val)])\n",
    "\n",
    "        result = []\n",
    "        ans = []\n",
    "        res = []\n",
    "        check(root,ans)\n",
    "        for x in result:\n",
    "            res.append(x[::-1])\n",
    "        return ''.join(min(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        maps={}\n",
    "        def updatepre(tree):\n",
    "            nonlocal maps\n",
    "            if not tree:\n",
    "                return\n",
    "            if tree.left:\n",
    "                maps[tree.left]=tree\n",
    "            if tree.right:\n",
    "                maps[tree.right]=tree\n",
    "            updatepre(tree.left)\n",
    "            updatepre(tree.right)\n",
    "        updatepre(root)\n",
    "\n",
    "        ans=\"\"\n",
    "        def dfs(tree):\n",
    "            nonlocal ans\n",
    "            if not tree.left and not tree.right:\n",
    "                cur=[]\n",
    "                flag=True\n",
    "                tmp=tree\n",
    "                while tmp in maps:\n",
    "                    cur.append(tmp.val)\n",
    "                    tmp=maps[tmp]\n",
    "                cur.append(root.val)\n",
    "                subans=\"\".join([chr(ord('a')+valcur) for valcur in cur])\n",
    "                if ans==\"\" or subans<ans:\n",
    "                    ans=subans\n",
    "                return\n",
    "            if tree.left:\n",
    "                dfs(tree.left)\n",
    "            if tree.right:\n",
    "                dfs(tree.right)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        ls = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        prevs, stack = {}, []\n",
    "        def dfs(node):\n",
    "            if node.left:\n",
    "                prevs[node.left] = node\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                prevs[node.right] = node\n",
    "                dfs(node.right)\n",
    "            if not node.left and not node.right:\n",
    "                stack.append(node)\n",
    "        dfs(root)\n",
    "        ans, cur, mi, ok = [], 0, 26, 0\n",
    "        while stack:\n",
    "            mi, tmp, ok = 26, [], 0\n",
    "            for node in stack:\n",
    "                if node.val < mi:\n",
    "                    tmp, mi, ok = [], node.val, 0\n",
    "                if node.val <= mi:\n",
    "                    if not node in prevs: ok = 1\n",
    "                    else: tmp.append(prevs[node])\n",
    "            ans.append(ls[mi])\n",
    "            if ok == 1: break\n",
    "            stack = tmp\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional\n",
    "from functools import cmp_to_key\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ll = []\n",
    "\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        \"\"\"\n",
    "\n",
    "        :param root:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ll = []\n",
    "        self.iter(root, ll)\n",
    "        ll2 = []\n",
    "        for i in self.ll:\n",
    "            res = [j for j in reversed(i)]\n",
    "            ll2.append(res)\n",
    "        \n",
    "        ret = None\n",
    "        def custcmp(a,b):\n",
    "            if len(a) == 0 and len(b) == 0:\n",
    "                return 0\n",
    "            if len(a) == 0:\n",
    "                return 1\n",
    "            if len(b) == 0:\n",
    "                return -1\n",
    "            \n",
    "            if a[0] > b[0]:\n",
    "                return -1\n",
    "            if b[0] > a[0]:\n",
    "                return 1\n",
    "            return custcmp(a[1:], b[1:])\n",
    "        ll2.sort(key=cmp_to_key(custcmp))\n",
    "        print(ll2)\n",
    "        ret = ll2[-1]\n",
    "        ret2 = ''\n",
    "        for i in ret:\n",
    "            ret2 += chr(97 + int(i))\n",
    "        return ret2\n",
    "\n",
    "    def iter(self, node, ll):\n",
    "        if node is None:\n",
    "            return\n",
    "        if node.left is None and node.right is None:\n",
    "            res = ll.copy()\n",
    "            res.append(node.val)\n",
    "            self.ll.append(res)\n",
    "            return\n",
    "        if node.left:\n",
    "            v1 = ll.copy()\n",
    "            v1.append(node.val)\n",
    "            self.iter(node.left, v1)\n",
    "        if node.right:\n",
    "            v1 = ll.copy()\n",
    "            v1.append(node.val)\n",
    "            self.iter(node.right, v1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        \"\"\"\n",
    "            25 \n",
    "           1   3\n",
    "          1 3  0 2\n",
    "        \"\"\"\n",
    "        # n_31 = TreeNode(1)\n",
    "        # n_32 = TreeNode(3)\n",
    "        # n_33 = TreeNode(0)\n",
    "        # n_34 = TreeNode(2)\n",
    "        # n_21 = TreeNode(1, n_31, n_32)\n",
    "        # n_22 = TreeNode(3, n_33, n_34)\n",
    "        # root = TreeNode(25, n_21, n_22)\n",
    "\n",
    "        root.parent = None\n",
    "        q = Queue()\n",
    "        q.put([root, (root.val,)])\n",
    "        routes = []\n",
    "        while not q.empty():\n",
    "            note, val_tuple = q.get()\n",
    "            print(val_tuple)\n",
    "            val = note.val\n",
    "            left = note.left\n",
    "            if left is not None:\n",
    "                left.parent = note\n",
    "                left_tuple = (left.val, ) + val_tuple\n",
    "                q.put([left, left_tuple])\n",
    "            right = note.right\n",
    "            if right is not None:\n",
    "                right.parent = note\n",
    "                right_tuple = (right.val, ) + val_tuple\n",
    "                q.put([right, right_tuple])\n",
    "            if left is None and right is None:\n",
    "                routes.append(val_tuple)\n",
    "        short_route = min(routes)\n",
    "        str_list = [chr(i + 97) for i in short_route]\n",
    "        result = \"\".join(str_list)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        M = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        if not root :\n",
    "            return \"\"\n",
    "        queue =[(root,M[root.val])]\n",
    "        result = []\n",
    "        while queue:\n",
    "            node,res = queue.pop(0)\n",
    "            if not node.left and not node.right:\n",
    "                result.append(res)\n",
    "            \n",
    "            if node.left:\n",
    "                queue.append((node.left,M[node.left.val]+res))\n",
    "\n",
    "            if node.right:\n",
    "                queue.append((node.right,M[node.right.val]+res))\n",
    "\n",
    "        result.sort()\n",
    "        return result[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:\n",
    "        letters = ascii_lowercase\n",
    "        def check(res):\n",
    "            for i, a in enumerate(res):\n",
    "                res[i] = ''.join([letters[i] for i in a])\n",
    "            return sorted(res)[0]\n",
    "            \n",
    "        self.res = []\n",
    "        def backtrack(node, path):\n",
    "            if node:\n",
    "                if not node.left and not node.right:\n",
    "                    self.res.append([node.val] + path)\n",
    "                    return\n",
    "                backtrack(node.left, [node.val] + path)\n",
    "                backtrack(node.right, [node.val] + path)\n",
    "        backtrack(root, [])\n",
    "        return check(self.res)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
